# 216.组合总和III
# 找出所有相加之和为n的k个数的组合，且满足下列条件：
# 只使用数字1到9
# 每个数字最多使用一次
#
# 返回所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
#
# 示例1:
# 输入: k = 3, n = 7
# 输出: [[1, 2, 4]]
# 解释:1 + 2 + 4 = 7
# 没有其他符合的组合了。
#
# 示例2:
# 输入: k = 3, n = 9
# 输出: [[1, 2, 6], [1, 3, 5], [2, 3, 4]]
# 解释:
# 1 + 2 + 6 = 9
# 1 + 3 + 5 = 9
# 2 + 3 + 4 = 9
# 没有其他符合的组合了。
#
# 示例3:
# 输入: k = 4, n = 1
# 输出: []
# 解释: 不存在有效的组合。
# 在[1, 9]
# 范围内使用4个不同的数字，我们可以得到的最小和是1 + 2 + 3 + 4 = 10，因为10 > 1，没有有效的组合。


class Solution:
    def combinationSum3(self, k: int, n: int):
        # 自己瞎咪咪摸出来的
        res = []
        path = []
        def backtracking(n,k,index,count):
            if len(path) == k:
                if sum(path) != n:
                    return
                else:
                    res.append(path[:])
                    return
            # 新加了剪枝操作
            stop_index = count - (k - len(path)) + 1
            for i in range(index,stop_index+1):
                path.append(i)
                backtracking(n,k,i+1,count)
                path.pop()
        backtracking(n,k,1,9)
        return res

    def combinationSum32(self, k: int, n: int):
        res = []
        path = []
        def backtracking(targetsum,k,sum_,startindex):
            if sum_ > targetsum: # 新追加的剪枝操作，处理的是上一个刚加的节点
                return
            if len(path) == k:
                if targetsum == sum_:
                    res.append(path[:])
                return # 不论是否相等，都要返回
            stop = 9 - (k - len(path)) + 2
            for i in range(startindex,stop):
                sum_ += i # 处理
                path.append(i) # 处理
                backtracking(targetsum, k, sum_, i+1) # 注意起始位置+1
                sum_ -= i  # 回溯
                path.pop() # 回溯
        backtracking(n, k, 0, 1)
        return res


    # def __init__(self):
    #     self.res = []
    #     self.sum_now = 0
    #     self.path = []
    #
    # def combinationSum33(self, k: int, n: int) -> [[int]]:
    #     self.backtracking(k, n, 1)
    #     return self.res
    #
    # def backtracking(self, k: int, n: int, start_num: int):
    #     if self.sum_now > n:  # 剪枝
    #         return
    #     if len(self.path) == k:  # len(path)==k时不管sum是否等于n都会返回
    #         if self.sum_now == n:
    #             self.res.append(self.path[:])
    #         return
    #     for i in range(start_num, 10 - (k - len(self.path)) + 1):
    #         self.path.append(i)
    #         self.sum_now += i
    #         self.backtracking(k, n, i + 1)
    #         self.path.pop()
    #         self.sum_now -= i




if __name__ == '__main__':
    tmp = Solution()
    k = 2#3
    n = 18
    # res = tmp.combinationSum3(k,n)
    res = tmp.combinationSum32(k,n)
    print(res)
